package com.atguigu.substring;

public class KMP {
    public int[] getNextArray(String str){
            int[] ret=new int[str.length()];
            ret[0]=-1;
            if(str.length()==1){
                return ret;
            }
            ret[1]=0;
            int j=1;
            int k=ret[j];
            while(j<str.length()-1){
                if(k<0 || str.charAt(j)==str.charAt(k)){
                    ret[++j]=++k;
                }else{
                    k=ret[k];
                }
            }
            return ret;
        }
    public int kmp(String str1,String str2){
        if(str1==null || str2==null|| str1.length()<str2.length()){
            return -1;
        }
        char[] chars1=str1.toCharArray();
        char[] chars2=str2.toCharArray();
        int i1=0;
        int i2=0;
        int[] next=getNextArray(str2);
        while(i1<str1.length() && i2<str2.length()){
            if(chars1[i1]==chars2[i2]){
                i1++;
                i2++;
            }else if(next[i2]==-1){  //next数的第0项默认为-1,此时跳到这步说明失配了，同时i2无法再往前跳了，需要i1++换一个开头
                i1++;
            }else{
                i2=next[i2]; //失配了进行跳转
            }
        }
        //i1越界或者 i2越界
        return i2==str2.length()?i1-i2:-1;
    }
}
